package com.sx.sx1.lintcode.day717;

import java.util.LinkedList;

public class LC368 {

    static class Solution {
        /**
         * @param expression: a list of strings
         * @return: an integer
         */
        public int evaluateExpression(String[] expression) {
            return f(expression,0).data;
        }

        public Info f(String[] exp,int i){
            LinkedList<String> ll = new LinkedList<>();
            int cur =0;
            Info info = new Info();
            while (i<exp.length && !exp[i].equals(")")){
                String s1 = exp[i];
                if(s1.equals(" ")){
                    i++;
                    continue;
                }

                if(s1.charAt(0) >='0' && s1.charAt(0)<='9') {
                    cur = Integer.valueOf(s1);
                    i++;
                }else if(!s1.equals("(")){
                    add(ll,cur);
                    ll.add(s1+"");
                    i++;
                }else{
                    info= f(exp,i+1);
                    i = info.idx+1;
                    cur = info.data;
                }
            }

            add(ll,cur);
            info.data= getData(ll);
            info.idx = i;
            return info;
        }

        public int getData(LinkedList<String> ll){
            int res =0;
            boolean add = true;
            String cur;

            while (!ll.isEmpty()){
                String top = ll.pollFirst();
                if(top.equals("+")) add =true;
                else if(top.equals("-")) add = false;
                else{
                    if(add) res+= Integer.valueOf(top);
                    else res-=Integer.valueOf(top);
                }
            }
            return res;
        }

        public void add(LinkedList<String> ll,int num){
            if(!ll.isEmpty()){
                if(ll.peekLast().equals("*")){
                    ll.pollLast();
                    num=Integer.valueOf(ll.pollLast())*num;
                }

              else  if (ll.peekLast().equals("/")) {
                    ll.pollLast();
                    num=Integer.valueOf(ll.pollLast())/num;
                }
            }
            ll.add(num+"");
        }
        static class Info{
            public int data;
            public int idx;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        String[] arr = {"2", "*", "6", "-", "(","23", "+", "7", ")", "/", "(", "1", "+", "2", ")"};
        System.out.println(obj.evaluateExpression(arr));
        String[] arr1 = {"4", "-", "(", "2","-", "3", ")", "*", "2", "+", "5", "/", "5"};
        System.out.println(obj.evaluateExpression(arr1));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有193条未读消息，请及时查看
368 · 表达式求值
算法
困难
通过率
26%

题目
题解15
笔记
讨论99+
排名
记录
描述
给一个用字符串表示的表达式数组，求出这个表达式的值。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


表达式只包含整数, +, -, *, /, (, ).

样例
样例 1:

对于表达式 `2*6-(23+7)/(1+2)`,
输入:
["2", "*", "6", "-", "(","23", "+", "7", ")", "/", "(", "1", "+", "2", ")"]
输出:
2
样例 2:

对于表达式 `4-(2-3)*2+5/5`,
输入:
["4", "-", "(", "2","-", "3", ")", "*", "2", "+", "5", "/", "5"]
输出:
7
标签
相关题目

1908
布尔表达式求值
困难

367
表达树构造
困难

370
将表达式转换为逆波兰表达式
中等

369
将表达式转换为波兰表达式
中等

719
计算最大值
中等

575
字符串解码
中等
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
349/1856
已开启智能提示
发起考试
45 分 00 秒
123456789

控制台
        历史提交

 */